package problem68;

import java.util.ArrayList;
import java.util.List;

//68.文本左右对齐
//https://leetcode.cn/problems/text-justification/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        int n = words.length;
        List<String> ret = new ArrayList<>();
        int i = 0;
        while (i < n) {
            int j = i;
            int cnt = words[i].length();
            // j-i : 最少空格数
            while (j + 1 < n && cnt + words[j + 1].length() + j + 1 - i <= maxWidth) {
                cnt += words[j + 1].length();
                j++;
            }
            int speceCount = maxWidth - cnt; // 空格总数数
            StringBuffer str = new StringBuffer();
            if (j >= n - 1) {
                // 处理最后一行
                for (int k = i; k <= j; k++) {
                    str.append(words[k]);
                    if (k < j) str.append(" ");
                }
                // 补空格
                appendSpace(str, maxWidth - str.length());
            } else {
                for (int k = i; k <= j; k++) {
                    str.append(words[k]);
                    //// 计算空格间距
                    if (k < j) {
                        int space = speceCount / (j - k);
                        if (speceCount % (j - k) != 0) space++;
                        speceCount -= space;
                        appendSpace(str, space);
                    }
                }
                // 补空格
                appendSpace(str, maxWidth - str.length());
            }
            ret.add(str.toString());
            i = j + 1;
        }
        return ret;
    }

    private void appendSpace(StringBuffer str, int n) {
        for (int i = 0; i < n; i++) {
            str.append(" ");
        }
    }
}
